export class ListNode {
  val: number;
  next: ListNode | null;
  random?: ListNode | null;
  constructor(val?: number, next?: ListNode | null, random?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
    this.random = random === undefined ? null : random;
  }
}

export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

export const generateNodeList = (list: (number | null)[]) => {
  const head = new ListNode();
  if (list[0] !== null) head.val = list[0];
  let tmp: ListNode = head;
  for (let i = 1; i < list.length; i += 1) {
    if (list[i] !== null) {
      let n = new ListNode(list[i] || undefined);
      tmp.next = n;
      tmp = n;
    }
  }
  return head;
};

export const generateBinaryTree = (list: (number | null)[]) => {
  const root = new TreeNode();
  if (list[0] !== null) root.val = list[0];
  let q = [root];
  for (let i = 1; i < list.length; i += 2) {
    let tmp = q.shift();
    if (tmp) {
      if (i < list.length && list[i] !== null) {
        let n = new TreeNode(list[i] || undefined);
        tmp.left = n;
        q.push(n);
      }
      if (i + 1 < list.length && list[i + 1] !== null) {
        let n = new TreeNode(list[i + 1] || undefined);
        tmp.right = n;
        q.push(n);
      }
    }
  }
  return root;
};

// 前序遍历树
export const preorderTraversal = (root: TreeNode | null) => {
  if (root) {
    console.log(root.val);
    preorderTraversal(root.left);
    preorderTraversal(root.right);
  } else {
    return null;
  }
};
